The present invention relates to a circuit and method for arbitration between channels competing for selection, and to a data processing system employing such a circuit.
It is common for electronic devices to be connected to a number of peripheral devices, or channels, and to select one channel for servicing at any one time. An example of this is found in the field of direct memory access (DMA) data transfer in a computer system, in which data is transferred by a number of different `slave` devices, or channels, primarily to and from the main memory, without using the central processing unit (CPU). Typically a DMA controller is used to supervise and control these data transfers. Bypassing the CPU usually allows higher data transfer rates and also frees the CPU for other processing tasks.
In a system in which a number of peripheral devices compete for use of a single DMA data bus, the DMA controller must arbitrate between simultaneously received DMA requests, granting one channel the use of the DMA data bus at any one time. This arbitration should be performed in a `fair` way, so that each requesting device is allocated a reasonable share of the use of the data bus.
A further complication arises when the DMA channels are arranged to request access to the DMA data bus in groups, rather than independently. This may occur, for example, when a number of DMA channels are arranged to transmit data on a single bus or along a single cable in a packet-multiplexed manner. In this case, requests from all the channels within the group will be received simultaneously, and all of these requests will be removed when any of the channels within the group is service. There will be a pause while the packet is transmitted, and then all of the channels in that group will request again. The DMA controller must allocate bus usage fairly within each group, as well as between groups.
One prior art request arbitration method is the so-called `rotating priority` or `round robin` approach, as used in several commercially available DMA controllers such as the Motorola MC6844 (described in `Motorola Microprocessor, Microcontroller and Peripheral Data, Volume II`, 1988 pages 3-1757 to 3-1773) and the Intel 8237A and 8257A (described in `Intel Microsystem Components Handbook--Microprocessors and Peripherals` Volume 1, pages 2-61 to 2-88). In this system each channel is assigned a priority value. At any time the requesting channel having the highest priority is allowed access to the DMA data bus; that channel is then assigned the lowest possible priority, and the priority of each of the other channels is incremented. The next DMA access is given to the new highest priority requesting channel.
The rotating priority scheme works well when the requesting channels are all independent, but does not provide fair arbitration between competing requests when the channels are organised into groups. In this latter situation, requests by some of the channels may never be serviced. This problem will be described further below with reference to certain of the accompanying drawings.
Another prior art arbitration scheme is described in GB 2202977, in which the channels transmit a priority value to a DMA controller on a separate arbitration bus. The controller then compares this value with one stored within the controller before deciding whether to grant DMA access to that channel.